/******************************************************************************
 This is a derivative work of the data structure presented in:
 
 http://www.cmcrossroads.com/bradapp/ftp/src/libs/C++/AvlTrees.html

 whose author is Brad Appleton (http://www.bradapp.net/). 
 
 See License.txt for license information about the use of the data
 structure.

 Please, note the links above were valid when this comment was written and 
 may not be valid at the time you read it.
 ******************************************************************************/

#ifndef TST_AVL_H
#define TST_AVL_H

#include <boost/iterator/reverse_iterator.hpp>
#include <boost/spirit/home/classic/debug.hpp>
#include <boost/spirit/home/classic/core/assert.hpp>
#include <utility>

#include "avl.h"
#include "avl_iterator.h"
#include "tst_avl_pair.h"

namespace cnome { namespace tst_avl {
 template <typename StringT, 
          typename T, 
          typename Pred,
          typename Alloc>
class tst_avl {
    typedef typename StringT::value_type char_t;

    typedef avlTree<char_t, T, Pred, Alloc> tree_type;
    typedef avlNode<char_t, T, Pred, Alloc> node_type;
    typedef std::size_t                     size_type;
    typedef typename Alloc:: template rebind<T>::other Alloc_T;

public:
    // typedefs:
    typedef StringT                           key_type;
    typedef T                                 data_type;
    typedef T                                 mapped_type;
    typedef std::pair<const StringT, T>       value_type;
    typedef Pred                              key_compare;
    typedef Alloc                             allocator_type;
    typedef tst_avl_iterator<StringT, T, Pred, Alloc>      iterator;
    typedef iterator const                    const_iterator;
    typedef boost::reverse_iterator<iterator> reverse_iterator;
    typedef reverse_iterator const            const_reverse_iterator;

    // Constructors
    tst_avl(): root(), m_size(0), end_(&root) {}

    explicit tst_avl(const key_compare& pred)
        : root(pred), m_size(0), end_(&root) {}	 // construct empty map from comparator

    tst_avl(const key_compare& pred, const allocator_type& al)
        : root(pred, al), m_size(0), end_(&root) {}  // construct empty map from comparator and allocator

    template<typename Iterator>
    tst_avl(Iterator first, Iterator last)
    : root(), m_size(0), end_(&root) {	// construct map from [first, last), defaults
        _DEBUG_RANGE(first, last);
        for (; first != last; ++first)
            this->insert(*first);
    }

    template<typename Iterator>
    tst_avl(Iterator first, Iterator last,
            const key_compare& pred)
    : root(pred), m_size(0), end_(&root) {	// construct map from [first, last), comparator
        _DEBUG_RANGE(first, last);
        for (; first != last; ++first)
            this->insert(*first);
    }

    template<typename Iterator>
    tst_avl(Iterator first, Iterator last,
            const key_compare& pred, const allocator_type& al)
    : root(pred, al), m_size(0), end_(&root) {	// construct map from [first, last), comparator, and allocator
        _DEBUG_RANGE(first, last);
        for (; first != last; ++first)
            this->insert(*first);
    }

    ~tst_avl() {
        clear();
    }

    template <typename Iterator>
    const_iterator
        find(Iterator first, Iterator last) const {
        const_iterator ret(&root);
        impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>& it  = const_cast<impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>&>(ret.base());
        std::size_t hwPos = 0;
        node_type ** tp = const_cast<node_type**>(&tst_Avl_TreeRoot());
        while (first != last && tp && *tp) {
            if ((tp = &node_type::find(root.m_pred, *first, const_cast<const node_type*&>(*tp))) && *tp ) {
                for (first++, hwPos = 1; first != last && hwPos < (*tp)->keySize() && *first == (*tp)->keyAddress()[hwPos]; first++, hwPos++);
                it.ptrNode = *tp;
                if (first == last)
                    return (*tp)->getData() && (hwPos == (*tp)->keySize())?const_iterator(it):end();
                else if (hwPos < (*tp)->keySize())
                    return end();
                tp = &(*tp)->subtree(MIDDLE);
                continue;
            }
            return end();
        }

#ifdef KEEP_ITER_KEY_UPDATED_AS_POSSIBLE
        if (tp&&*tp&&(*tp)->getData()) {
            it.valueFirst = key_type(first, last);
            it.outDated &= impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>::OUTDATED_ALL & ~impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>::OUTDATED_KEY;
        }
#endif
        return tp&&*tp&&(*tp)->getData()?const_iterator(it):end();
    }

    template <typename Iterator>
    iterator
        find(Iterator first, Iterator last) {
        return const_cast<const tst_avl*>(this)->find(first, last);
    }

    const_iterator
        find(const key_type& key) const {
        return find(key.begin(), key.end());
    }

    iterator
        find(const key_type& key) {
        return const_cast<const tst_avl*>(this)->find(key);
    }

    std::pair<iterator, bool> 
        insert( const value_type& v ) {
        typename StringT::const_iterator first = v.first.begin();
        typename StringT::const_iterator last = v.first.end();
        T& val = const_cast<T&>(v.second);
        std::pair<iterator, bool> ret;
        
        bool &inserted = ret.second;
        inserted = true;
        impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>& it = const_cast<impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>&>(ret.first.base());
        node_type** tp = &(tst_Avl_TreeRoot());
        while (first != last) {
            int i = 0;
            node_type** mp = &node_type::find(root.m_pred, *first, const_cast<const node_type*&>(*tp));
            if ((*mp) != 0) {
                size_t hwPos = 1;
                for ( first++, hwPos = 1; first != last && hwPos < (*mp)->keySize() && *((*mp)->keyAddress()+hwPos) == *first; hwPos++)
                    first++;
                if (hwPos < (*mp)->keySize())
                    splitNode(*mp, hwPos);
                it.ptrNode = *mp;
                if (first == last && hwPos == (*mp)->keySize()) {
					if (!(*mp)->getData()) {  // If found key, doesn't insert
                        (*mp)->getData() = m_alloc_t.allocate(1);
                        m_alloc_t.construct((*mp)->getData(), val);
                        m_size++;
                    }
                    else {
                        inserted = false;
#ifdef KEEP_ITER_KEY_UPDATED_AS_POSSIBLE
                        it.valueFirst = v.first;
                        it.outDated &= impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>::OUTDATED_ALL & ~impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>::OUTDATED_KEY;
#endif
                        return ret;
                    }
                    break; 
                }
                else {
                    tp = &(*mp)->subtree(MIDDLE);
                    if (!*tp) {
                        it.ptrNode = insertNode(first, last, tp, val, *mp);
                        m_size++;
                        break;
                    }
                }
            }
            else {
                if (tst_Avl_TreeRoot() == 0)
                    it.ptrNode = insertNode(first, last, tp, val, root.nillNode);
                else {
                    typename Alloc_T::pointer tmp = m_alloc_t.allocate(1);
                    m_alloc_t.construct(tmp, val);
                    it.ptrNode = node_type::insert(root.m_pred, first, last, tmp, *tp);
                }
                m_size++;
                break;
            }
        }

#ifdef KEEP_ITER_KEY_UPDATED_AS_POSSIBLE
        it.valueFirst = v.first;
        it.outDated &= impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>::OUTDATED_ALL & ~impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>::OUTDATED_KEY;
#endif

#ifdef AVL_TST_CHECK
        check();
#endif

        return ret;
    } 

    iterator erase(iterator it) {
        typename iterator::base_type& l_it = const_cast<typename iterator::base_type&>(it.base());
        if (l_it.is_atend() || !l_it.ptrNode->getData())  // TODO: Use ASSERT to verify that getData() != 0
            return end();

        iterator next(it);
        next++;

        // erase symbol
        m_alloc_t.destroy(l_it.ptrNode->getData());
        l_it.ptrNode->getData() = 0;

        // The symbol was found and "removed" now adequate the tree.
        // erase nodes with no data and middle child, because they
        // are either tail nodes or nodes that are not part of larger
        // keys.
        node_type** node, **prtNode;
        for (node = prtNode = &l_it.ptrNode->myLinkInParent();
             !(*node)->isNill() && !(*node)->getData() && !(*node)->subtree(MIDDLE);) {
             prtNode = &(*prtNode)->parent->myLinkInParent();
             BOOST_SPIRIT_ASSERT( (    (*prtNode)->isNill()
                                    || (*prtNode)->subtree((*node)->myDirInParent())==*node
                                  ) && "Tst_Avl internal error" );
             node_type::erase(root.m_pred, *node);
             node = prtNode;
        }
        --m_size; // Having removed an item, reduce m_size by one
        
        if (    !(*node)->isNill() && !(*node)->parent->isNill()
             && !(*node)->subtree(LEFT)  && !(*node)->subtree(RIGHT) 
             //&& !(*node)->getData()
             && (*node)->myDirInParent() == MIDDLE
             && !(*node)->parent->getData()) 
             if (*node == next.base().ptrNode || (*node)->parent == next.base().ptrNode)
                 const_cast<typename iterator::base_type&>(next.base()).ptrNode = mergeNodes(*node);
             else
                 mergeNodes(*node);

#ifdef AVL_TST_CHECK
        check();
#endif

        return next;
    }

    template <typename Iterator>
    void
        erase(
        Iterator first
        , Iterator last) {
        iterator it = find(first, last);
        erase(it);
    }

    size_type erase(const StringT& k) {
        typename StringT::const_iterator first = k.begin();
        typename StringT::const_iterator last = k.end();

        size_type nKeys;
        iterator it;
        for (nKeys = 0; (it = find(first, last)) != end(); nKeys++)
            erase(it);

        return nKeys;
     }

    mapped_type& operator[](const key_type& key) {	
		// find element matching _Keyval or insert with default mapped
        
        typename tst_avl<StringT, T>::iterator it = this->find(key);
        if (it == this->end()) {
            mapped_type tmp;
            it = this->insert(typename tst_avl<StringT, T>::value_type(key, tmp)).first;
        }
        
        return ((*it).second);

        /*--------- The solution bellow was abandoned because the mapped_type constructor could 
        //--------- be expensive.
        mapped_type tmp;
        return insert(typename tst_avl<StringT, T>::value_type(key, tmp)).first->second;
        */
    }
    
    size_type size() const { return m_size; }
    bool empty() const { return size() == 0; }
    size_type max_size() const {	// return maximum possible length of sequence
        return (this->_Alval.max_size());
    }

	void clear() {  // TODO: Improve performance of this method.
       for (iterator it = begin(); it != end(); it = erase(it));
    }

	const_iterator begin() const {  // TODO: Review this method
        const_iterator it(&root);
        impl::tst_avl_iterator_impl<StringT, T, Pred, Alloc>& l_it = const_cast<impl::tst_avl_iterator_impl<StringT, T, Pred, Alloc>&>(it.base());
        l_it.ptrNode = const_cast<node_type*>(tst_Avl_TreeRoot());
        if (!l_it.ptrNode) {
            l_it.ptrNode = const_cast<node_type*>(root.nillNode);
            return it;
        }
        l_it.goFirstOne();

        return it;
    }

    iterator begin() {
        return const_cast<const tst_avl*>(this)->begin();
    }


    const_iterator end() const {
        return end_;
    }

    iterator end() {
        return const_cast<const tst_avl*>(this)->end();
    }

    const_reverse_iterator rbegin() const {
        return const_reverse_iterator(end());
    }

    reverse_iterator rbegin() {
        return reverse_iterator(end());
    }

    const_reverse_iterator rend() const {
        return const_reverse_iterator(begin());
    }

    reverse_iterator rend() {
        return reverse_iterator(begin());
    }

    // Extra finds

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    template <typename IteratorT>
    const_iterator
        find_longest(IteratorT& first, const IteratorT& last) const {
        impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc> it(&root);
        std::string aux;
        std::size_t hwPos = 0;
        node_type ** tp = const_cast<node_type**>(&tst_Avl_TreeRoot());
        if ((*tp)->isNill())
            return const_iterator(it);
        while (first != last && tp && *tp) {
            if (!(tp = &node_type::find(root.m_pred, *first, const_cast<const node_type*&>(*tp))) || !*tp ) //!= &node_type::0)
                break;
            else {
                aux += *first;
                for (first++, hwPos = 1; first != last && hwPos < (*tp)->keySize() && *first == (*tp)->keyAddress()[hwPos]; first++, hwPos++)
                    aux += *first;
                if (first == last) // Exact match
                    return const_iterator(it);
                else if (hwPos < (*tp)->keySize())
                    break;
                if ((*tp)->getData()) {
                    it.valueFirst += aux;
                    it.ptrNode = *tp;
                    aux = "";
                }
                tp = &(*tp)->subtree(MIDDLE);
            }
        }
        if (it.valueFirst.empty())
            return end();

        return const_iterator(it);
    }

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    template <typename IteratorT>
    iterator 
        find_longest(IteratorT& first, const IteratorT& last) {
        return const_cast<const tst_avl*>(this)->find_longest(first, last);
    }

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    const_iterator
        find_longest(key_type const &key) const {
        typename key_type::const_iterator beg = key.begin();
        typename key_type::const_iterator end_ = key.end();
        return find_longest(beg, end_);
    }

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    iterator 
        find_longest(key_type const & key) {
        return const_cast<const tst_avl*>(this)->find_longest(key);
    }

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    template <typename IteratorT>
    const_iterator
        find_smallest(IteratorT& first, const IteratorT& last) const {
        impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc> it(&root);
        std::size_t hwPos = 0;
        node_type ** tp = const_cast<node_type**>(&tst_Avl_TreeRoot());
        if ((*tp)->isNill())
            return const_iterator(it);
        while (first != last && tp && *tp) {
            if (!(tp = &node_type::find(root.m_pred, *first, const_cast<const node_type*&>(*tp))) || !*tp ) //!= &node_type::0)
                return end();
            else {
                it.valueFirst += *first;
                for (first++, hwPos = 1; first != last && hwPos < (*tp)->keySize() && *first == (*tp)->keyAddress()[hwPos]; first++, hwPos++)
                    it.valueFirst += *first;

                it.ptrNode = *tp;
                if (first == last) {
                    for (; hwPos < (*tp)->keySize(); hwPos++)
                        it.valueFirst += (*tp)->keyAddress()[hwPos];
                    break;
                }
                else if (hwPos < (*tp)->keySize())
                    return end();
                tp = &(*tp)->subtree(MIDDLE);
            }
        }
        if (!it.ptrNode->getData())
           it.advance();

        return const_iterator(it);
    }

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    template <typename IteratorT>
    iterator 
        find_smallest(IteratorT& first, const IteratorT& last) {
        return const_cast<const tst_avl*>(this)->find_smallest(first, last);
    }

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    const_iterator
        find_smallest(key_type const &key) const {
        typename key_type::const_iterator beg  = key.begin();
        typename key_type::const_iterator end_ = key.end();
        return const_cast<tst_avl*>(this)->find_smallest(beg, end_);
    }

    // Exact longest match anchored at beginning-of-key (or full match, if
    // stored in the TST).
    iterator 
        find_smallest(key_type const & key) {
        return const_cast<const tst_avl*>(this)->find_smallest(key);
    }

    void check() {
        avlTree<char_t, T, Pred, Alloc>* avlTree = &root;
        if (avlTree)
            avlTree->check();
    }

 private:
    tree_type root;
    size_type m_size;
    Alloc_T   m_alloc_t;
    const_iterator end_;

    node_type*& tst_Avl_TreeRoot() const {
        return root.treeRoot();
    }

    iterator
        findEx(const key_type& key, node_type**& node, node_type**& prtNode) {
        typename key_type::const_iterator& first = key.begin();
        typename key_type::const_iterator& last = key.end();

        const_iterator ret(&root);
        impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>& it  = const_cast<impl::tst_avl_iterator_impl<StringT,T, Pred, Alloc>&>(ret.base());
        std::size_t hwPos = 0;
        prtNode = &tst_Avl_Tree_NillNode();
        node = const_cast<node_type**>(&tst_Avl_TreeRoot());
        while (first != last && node && *node) {
            if (node_type::findEx(root.m_pred, *first, *node, prtNode) && *node ) {
                for (first++, hwPos = 1; first != last && hwPos < (*node)->keySize() && *first == (*node)->keyAddress()[hwPos]; first++, hwPos++);
                it.ptrNode = node;
                if (first == last)
                    return (*node)->getData()?const_iterator(it):end();
                else if (hwPos < (*node)->keySize())
                    return end();
                prtNode = node;
                node = &(*node)->subtree(MIDDLE);
                continue;
            }
            return end();
        }
        return node&&*node&&(*node)->getData()?const_iterator(it):end();
    }

    node_type*& tst_Avl_Tree_NillNode() const {
        return const_cast<node_type*&>(root.nillNode);
    }

    node_type*& insertNode(  typename StringT::const_iterator& first, typename StringT::const_iterator& last, node_type**& node, T& val, node_type* prtNode) {
        *node = node_type::createAvlNode(first, last);
        (*node)->setKey(first, last);
        (*node)->getData() = m_alloc_t.allocate(1);
        m_alloc_t.construct((*node)->getData(), val);
        (*node)->parent = prtNode;	

        return *node;
    }

private:
    node_type*& splitNode(node_type*& node, std::size_t keyPos) {
        if (node->keySize() == 1) 
            return node; // Can't split a node with key of size 1
        if (keyPos < 0)
            return node; // Can't split a node before the first character
        if (node->keySize() <= keyPos)
            return node; // Can't split a node after the last character

        node_type* nodeP = node_type::createAvlNode(keyPos);
        nodeP->setKey(node->keyAddress(), nodeP->keySize());
        nodeP->setBal(node->getBal());
        node_type* nodeC = node_type::createAvlNode(node->keySize()-keyPos);
        nodeC->setKey(node->keyAddress() + keyPos, nodeC->keySize()); 

        nodeP->parent = node->parent;
        nodeP->subtree(LEFT) = node->subtree(LEFT);
        if (node->subtree(LEFT))
            node->subtree(LEFT)->parent = nodeP;
        nodeC->subtree(MIDDLE) = node->subtree(MIDDLE);
        if (node->subtree(MIDDLE))
            node->subtree(MIDDLE)->parent = nodeC;
        nodeP->subtree(RIGHT) = node->subtree(RIGHT);
        if (node->subtree(RIGHT))
            node->subtree(RIGHT)->parent = nodeP;
        nodeC->getData() = node->getData();
        nodeP->subtree(MIDDLE) = nodeC;
        nodeC->parent = nodeP;

        operator delete(node,0);
        node = nodeP;

        return node;
    }

    node_type*& mergeNodes(node_type*& node) {
        node_type*& prtNode = node->parent->myLinkInParent();

        std::size_t newKeySz = prtNode->keySize() + node->keySize();
        node_type* newNode = node_type::createAvlNode(newKeySz);
        newNode->setKeySize(newKeySz);
        memcpy(newNode->keyAddress(), prtNode->keyAddress(), prtNode->keySize()*sizeof(char_t));
        memcpy(newNode->keyAddress()+prtNode->keySize(), node->keyAddress(), node->keySize()*sizeof(char_t));
        newNode->getData() = prtNode->getData();
        newNode->setBal(prtNode->getBal());
        newNode->parent = prtNode->parent;
        newNode->subtree(LEFT) = prtNode->subtree(LEFT);
        if (prtNode->subtree(LEFT))
            prtNode->subtree(LEFT)->parent = newNode;
        newNode->subtree(RIGHT) = prtNode->subtree(RIGHT);
        if (prtNode->subtree(RIGHT))
            newNode->subtree(RIGHT)->parent = newNode;
        newNode->subtree(MIDDLE) = node->subtree(MIDDLE);
        if (node->subtree(MIDDLE))
            node->subtree(MIDDLE)->parent = newNode;

        node->parent = 0;
        node->subtree(MIDDLE) = 0;
        operator delete(node, 0);

        prtNode->parent = 0;
        prtNode->subtree(LEFT) = 0;
        prtNode->subtree(MIDDLE) = 0;
        prtNode->subtree(RIGHT) = 0;
        operator delete(prtNode, 0);

        prtNode = newNode;

        return prtNode;
    }

};

// range interface to add
template <typename Char, typename Range, typename T>
void add(tst_avl<Char, T>& tree, Range const& rng, T const& val) {
    tree.add(rng.begin(), rng.end(), val);
}

// range interface to find
template <typename Char, typename Range, typename T>
typename tst_avl<Char, T>::data_type const&
    find(tst_avl<Char, T> const& tree, Range const& rng) {
    return tree.find(rng.begin(), rng.end());
}
}}  // cnome::tst_avl

#endif // TST_AVL_H

